/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXI30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=XMAS25/FONT#8=FIX25



␈↓ α∧␈↓α␈↓ ¬⊗A Classification of Problems in AI

␈↓ α∧␈↓␈↓ αTThe␈αobject␈α
of␈αthis␈αclassification␈α
of␈αproblems␈αpartly␈α
to␈αshow␈αthat␈α
most␈αof␈αthe␈α
work␈αin␈αAI␈α
has
␈↓ α∧␈↓concentrated␈αon␈αa␈αsmall␈αclass␈αof␈αproblems␈αbut␈αalso␈αwith␈αthe␈αidea␈αthat␈αeach␈αnew␈αdifficulty␈αcan␈αbest
␈↓ α∧␈↓be considered apart from the others.

␈↓ α∧␈↓␈↓ αTThe␈α⊂first␈α⊃classification␈α⊂is␈α⊂based␈α⊃on␈α⊂the␈α⊂dichotomy␈α⊃-␈α⊂physical␈α⊂vs.␈α⊃mental.␈α⊂ A␈α⊃problem␈α⊂is
␈↓ α∧␈↓considered␈αphysical␈αif␈αthe␈αinformation␈αpresented␈αis␈αentirely␈αphysical,␈αi.e.␈α about␈αphysial␈αstates␈αand
␈↓ α∧␈↓the␈α
effects␈α
of␈α
physical␈α
actions.␈α
 The␈α
problem-solver␈α
may␈α
have␈α
to␈α
think,␈α
but␈α
it␈α
has␈α
only␈α∞to␈α
think
␈↓ α∧␈↓about␈αthe␈αphysical␈αeffects␈αof␈αits␈αactions␈αand␈αthose␈αof␈αothers.␈α In␈αa␈αmental␈αproblem,␈αone␈αhas␈αalso␈αto
␈↓ α∧␈↓think␈α
about␈α
knowledge␈α(where␈α
it␈α
is,␈α
who␈αhas␈α
it,␈α
and␈α
how␈αto␈α
get␈α
it)␈α
and␈αwants,␈α
e.g.␈α
what␈α
does␈αhe
␈↓ α∧␈↓want.␈α
 Naturally␈α
a␈α
mental␈α
problem␈α
may␈α
have␈α
a␈α
physical␈α
part,␈α
so␈α
to␈α
declare␈α
a␈α
problem␈α
physical␈α
is␈α
to
␈↓ α∧␈↓reduce␈α
it␈α
to␈α
a␈α
subdomain.␈α Perhaps␈α
the␈α
case␈α
when␈α
the␈α
solver␈αmust␈α
think␈α
only␈α
about␈α
its␈α
own␈αlack␈α
of
␈↓ α∧␈↓knowledge,␈α⊃and␈α⊂not␈α⊃about␈α⊃the␈α⊂location␈α⊃of␈α⊃knowledge␈α⊂in␈α⊃telephone␈α⊃books␈α⊂and␈α⊃other␈α⊃people␈α⊂is
␈↓ α∧␈↓special.

␈↓ α∧␈↓␈↓ αTThe␈αsecond␈α
classification␈αis␈αstatic␈α
vs.␈αdynamic.␈α A␈α
static␈αproblem␈αis␈α
one␈αwhere␈α
certain␈αfacts
␈↓ α∧␈↓about␈αa␈αsituation␈αare␈αknown,␈αand␈αthe␈αproblem␈αis␈αto␈αanswer␈αcertain␈αquestions␈αabout␈αthat␈αsituation.
␈↓ α∧␈↓In dynamic problems the situation changes.

␈↓ α∧␈↓␈↓ αTA␈α
popular␈α
subclass␈α
of␈αdynamic␈α
problems␈α
is␈α
called␈α␈↓↓quasi-static.␈↓␈α
In␈α
a␈α
quasi-static␈αproblem,␈α
the
␈↓ α∧␈↓solver␈α
must␈α∞make␈α
a␈α∞move␈α
in␈α∞a␈α
situation,␈α∞and␈α
this␈α
results␈α∞in␈α
a␈α∞new␈α
situation.␈α∞ His␈α
problem␈α∞is␈α
to
␈↓ α∧␈↓make␈αa␈αsequence␈αof␈αmoves␈αleading␈αto␈αa␈α
situation␈αthat␈αsatisfies␈αa␈αgoal␈αcondition.␈α Time␈αand␈α
actions
␈↓ α∧␈↓are␈αdiscrete,␈αand␈α
the␈αsolver␈αdoesn't␈α
have␈αto␈αconsider␈α
several␈αprocesses␈αgoing␈α
on␈αat␈αonce,␈αperhaps␈α
at
␈↓ α∧␈↓unknown relative rates.

␈↓ α∧␈↓␈↓ αTMost␈α∀of␈α∀the␈α∀problems␈α∀considered␈α∀in␈α∀AI␈α∀research␈α∀have␈α∀been␈α∀quasi-static,␈α∃and␈α∀people
␈↓ α∧␈↓sometimes␈αformulate␈αthe␈α
AI␈αproblem␈αas␈α
though␈αall␈αproblems␈α
were␈αquasi-static.␈α I'll␈αstrengthen␈α
that
␈↓ α∧␈↓remark; I know of no AI work on truly dynamic problems.

␈↓ α∧␈↓␈↓ αTWithin␈α∪the␈α∪quasi-static␈α∪problems,␈α∪we␈α∀can␈α∪make␈α∪some␈α∪distinctions.␈α∪ First,␈α∀the␈α∪required
␈↓ α∧␈↓solution␈α∂may␈α∂be␈α∂a␈α∂sequence␈α∂of␈α∂moves,␈α∂and␈α∂this␈α∂is␈α∂presumably␈α∂simpler␈α∂than␈α∂the␈α∂case␈α∂when␈α∞the
␈↓ α∧␈↓solution␈αis␈α
a␈αprogram,␈αe.g.␈α
␈↓↓go␈αSouth␈α
on␈αEl␈αCamino␈α
until␈αyou␈α
come␈αto␈αa␈α
Mobil␈αgas␈α
station␈↓.␈α Second,
␈↓ α∧␈↓the␈α
state␈αof␈α
the␈α
system␈αmay␈α
be␈α
completely␈αknown␈α
or␈α
not␈αas␈α
discussed␈α
by␈αRobert␈α
C.␈α
Moore␈α(1975)␈α
in
␈↓ α∧␈↓his␈αM.I.T.␈αM.S.␈αthesis.␈α As␈αMoore␈αpoints␈αout,␈αagain␈αmost␈αwork␈αhas␈αbeen␈αconcentrated␈αon␈αthe␈αeasy
␈↓ α∧␈↓case of complete knowledge.

␈↓ α∧␈↓␈↓ αTIt␈α∩seems␈α∩worthwhile␈α∩to␈α∩give␈α∩some␈α∩examples␈α∩of␈α∩problems␈α∩that␈α∩embody␈α∩the␈α∪less␈α∩studied
␈↓ α∧␈↓features, but which are still not too difficult.

␈↓ α∧␈↓REFERENCES:

␈↓ α∧␈↓Moore,␈α∪Robert␈α∪C.␈α∪(1975),␈α∪␈↓↓Reasoning␈α∪From␈α∪Incomplete␈α∪Knowledge␈α∪in␈α∪a␈α∀Procedural␈α∪Deduction
␈↓ α∧␈↓↓System␈↓. Artificial Intelligence Laboratory, M.I.T.





␈↓ α∧␈↓␈↓ ε|1␈↓ ∧